use crate::new_list1::{List, Node};
use crate::new_list2::{RcLink, RcList};
use crate::stools::{random_array, random_num};
use std::cmp::Ordering;

/// 在单链表和双链表中删除倒数第 K 个节点 【题目】
/// 分别实现两个函数，一个可以删除单链表中倒数第 K 个节点，另一个可以删除双链表中倒 数第 K 个节点。
/// 【要求】
/// 如果链表长度为 N，时间复杂度达到 O(N)，额外空间复杂度达到 O(1)。
fn remove_last_k(head: &mut List, mut last_k: i32) {
    if last_k < 1 {
        return;
    }

    let mut curlink = head.as_mut();
    while let Some(node) = curlink {
        curlink = node.next.as_mut();
        last_k -= 1;
    }

    match last_k.cmp(&0) {
        Ordering::Greater => return,
        Ordering::Equal => {
            if let Some(mut node) = head.head.take() {
                head.head = node.next.take();
            }
        }
        Ordering::Less => {
            curlink = head.as_mut();
            last_k += 1;
            while last_k != 0 {
                last_k += 1;
                if let Some(node) = curlink {
                    curlink = node.next.as_mut();
                }
            }
            if let Some(node) = curlink {
                if let Some(next) = node.next.take() {
                    node.next = next.next;
                }
            }
        }
    }
}

/// 双指针：
/// slow指向删除节点的前一个节点，fast：先走 k+1步，当fast=None时，slow是前一个节点
/// 双指针只能再clone()出一个链表，否则只能是两个只读指针同时指向一个链表，可变指针不能出现
/// 计数法：
/// 用指针先记录整个链表长度，再计算从头走到倒数第k个前一个节点要走多少步
fn remove_last_k_pointer(head: &mut List, last_k: i32) {
    if last_k < 1 {
        return;
    }

    let mut curlink = head.as_mut();
    let mut k: i32 = 0;
    while let Some(node) = curlink {
        curlink = node.next.as_mut();
        k += 1;
    }
    k -= last_k;

    match k.cmp(&0) {
        Ordering::Less => return,
        Ordering::Equal => {
            if let Some(mut node) = head.head.take() {
                head.head = node.next.take();
            }
        }
        Ordering::Greater => {
            curlink = head.as_mut();
            while k > 1 && let Some(node) = curlink {
                k -= 1;
                curlink = node.next.as_mut();
            }

            if let Some(node) = curlink {
                if let Some(next) = node.next.take() {
                    node.next = next.next;
                }
            }
        }
    }
}

/// 删除链表的中间节点和 a/b 处的节点
/// 【题目】
/// 给定链表的头节点 head，实现删除链表的中间节点的函数。
/// 例如：
/// None ro 1: 不删除任何节点；
/// 1->2，删除节点 1；
/// 1->2->3，删除节点 2；
/// 1->2->3->4，删除节点 2；
/// 1->2->3->4->5，删除节点 3；
fn remove_middle_node(list: &mut List) {
    if list.is_none() {
        return;
    }

    if let Some(node) = list.head.as_mut() {
        if node.next.is_none() {
            return;
        }
    }

    let mut nodes: usize = 0;
    let mut curlink = list.as_mut();
    while let Some(node) = curlink {
        nodes += 1;
        curlink = node.next.as_mut();
    }
    if nodes == 2 {
        if let Some(node) = list.head.take() {
            list.head = node.next;
        }
        return;
    }

    let mut delete_front = (nodes + 1) / 2 - 2;
    curlink = list.as_mut();
    while delete_front > 0 && let Some(node) = curlink {
        delete_front -= 1;
        curlink = node.next.as_mut();
    }

    if let Some(node) = curlink {
        if let Some(next) = node.next.take() {
            node.next = next.next;
        }
    }
}

/// 进阶：
/// 给定链表的头节点 head、整数 a 和 b，实现删除位于 a/b 处节点的函数例如：
/// 链表：1->2->3->4->5，假设 a/b 的值为 r。
/// 如果 r 等于 0，不删除任何节点；
/// 如果 r 在区间(0, 1/5]上，删除节点 1；
/// 如果 r 在区间(1/5, 2/5]上，删除节点 2；
/// 如果 r 在区间(2/5, 3/5]上，删除节点 3；
/// 如果 r 在区间(3/5, 4/5]上，删除节点 4
/// 如果 r 在区间(4/5, 1]上，删除节点 5
/// 如果 r 大于 1，不删除任何节点
fn remove_node_partition(list: &mut List, a: usize, b: usize) {
    if list.is_none() || a > b {
        return;
    }

    let mut n: usize = 0;
    let mut curlink = list.as_mut();
    while let Some(node) = curlink {
        n += 1;
        curlink = node.next.as_mut();
    }

    // 如果是 remove_node_idx 则是偏移
    // 这是编号，remove_node=1 表示要删除的是开头的第1个节点
    let mut remove_node_no = ((a as f32 * n as f32) / b as f32).ceil() as usize;
    print!("remove[{}]: ", remove_node_no);

    curlink = list.as_mut();
    match remove_node_no.cmp(&1) {
        Ordering::Greater => {
            // 停在要删除节点的前一个
            // 如果 remove_node_no = 1 表示指针在要删除的节点上，则remove_node_no是编号，
            // 如果remove_node_idx = 0表示指针在删除节点上，则remove_node_idx是偏移
            while remove_node_no > 2 && let Some(node) = curlink {
                remove_node_no -= 1;
                curlink = node.next.as_mut();
            }
            if let Some(node) = curlink && let Some(next) = node.next.take() {
                    node.next = next.next;
            }
        }
        Ordering::Equal => {
            if let Some(node) = curlink {
                list.head = node.next.take();
            }
        }
        Ordering::Less => return,
    }
}

/// 反转单向链表
fn rev_list(list: &mut List) {
    let mut prev: Option<Box<Node>> = None;
    let mut cur = list.head.take();
    let mut next: Option<Box<Node>>;

    while let Some(mut node) = cur {
        next = node.next.take();
        node.next = prev;
        prev = Some(node);
        cur = next;
    }

    list.head = prev;
}

/// 反转部分单向链表
/// 【题目】
/// 给定一个单向链表的头节点 head，以及两个整数 from 和 to，在单向链表上把第 from 个节
/// 点到第 to 个节点这一部分进行反转。
/// 例如：
/// 1->2->3->4->5->null，from=2，to=4
/// 调整结果为：1->4->3->2->5->null
/// 再如：
/// 1->2->3->null，from=1，to=3
/// 调整结果为：3->2->1->null
/// 【要求】
/// 1．如果链表长度为 N，时间复杂度要求为 O(N)，额外空间复杂度要求为 O(1)。
/// 2．如果不满足 1<=from<=to<=N，则不用调整。
fn rev_part_list(list: &mut RcList, from: usize, to: usize) {
    if list.head.is_none() || from < 1 || from >= to {
        print!("参数非法 ");
        return;
    }

    let mut n: usize = 0;
    let mut tolink: RcLink = RcLink(None);
    let mut fromlink: RcLink = RcLink(None);
    let mut start: RcLink = RcLink(None);
    let mut end: RcLink = RcLink(None);
    let mut prev: RcLink = RcLink(None);
    let mut next;
    let mut cur = list.head.clone();

    while let Some(node) = cur.as_ref() {
        n += 1;

        (n + 1 == from).then(|| start = RcLink(Some(node.clone())));
        (n == from).then(|| fromlink = RcLink(Some(node.clone())));
        (n == to).then(|| tolink = RcLink(Some(node.clone())));
        if n == to + 1 {
            end = RcLink(Some(node.clone()));
            break;
        }

        next = node.borrow().next.clone();
        if from <= n && n <= to {
            node.borrow_mut().next = prev.clone();
            prev = RcLink(Some(node.clone()));
        }
        cur = next;
    }

    (n < to).then(|| tolink = prev);
    if from == 1 {
        list.head = tolink
    } else {
        start.as_ref().map(|node| node.borrow_mut().next = tolink);
    }

    fromlink.as_ref().map(|node| node.borrow_mut().next = end);
}

/// 翻转部分列表
fn rev_part_vec(v: &mut Vec<i32>, mut from: usize, mut to: usize) {
    if from < 1 || from >= to || from > v.len() {
        print!("参数非法 ");
        return;
    }
    if to > v.len() {
        to = v.len();
    }

    while from < to {
        v.swap(from - 1, to - 1);
        from += 1;
        to -= 1;
    }
}

/// 环形单链表的约瑟夫问题 【题目】
/// 据说著名犹太历史学家 Josephus 有过以下故事:
/// 在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，
/// 于是决定了一 种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，
/// 然后再由下 一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，
/// 那个人可以 自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整 个自杀过程。
/// 输入:一个环形单向链表的头节点 head 和报数的值 m。 返回:最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉。
fn josephus_kill(list: &mut RcList, step: usize) {
    if step < 1 || list.head.is_none() {
        return;
    }

    let mut prev: RcLink = list.head.clone();
    let mut cur: RcLink = prev.move_step(1);
    let mut n: usize = 1;

    // 找 head 的 prev
    while cur != list.head {
        prev = cur.clone();
        cur = cur.move_step(1);
    }
    println!("list.head.prev: {}", prev);

    while prev != cur {
        while n != step {
            prev = cur.clone();
            cur = cur.move_step(1);
            n += 1;
        }
        print!("删除{}:", cur);

        prev.as_ref().unwrap().borrow_mut().next = cur.as_ref().unwrap().borrow().next.clone();
        cur = prev.as_ref().unwrap().borrow().next.clone();
        println!("{}", list);
        n = 1;
    }

    list.head = prev;
}

/// 判断一个链表是否为回文结构
/// 【题目】
/// 给定一个链表的头节点 head，请判断该链表是否为回文结构。 例如:
/// 1->2->1，返回 true。
/// 1->2->2->1，返回 true。
/// 15->6->15，返回 true。
/// 1->2->3，返回 false。
/// 进阶:
/// 如果链表长度为 N，时间复杂度达到 O(N)，额外空间复杂度达到 O(1)。
fn is_palindrome_stack(list: &mut List) -> bool {
    let mut curlink = list.head.as_ref();
    let mut stack: Vec<i32> = vec![];
    while let Some(node) = curlink {
        stack.push(node.elem);
        curlink = node.next.as_ref();
    }

    curlink = list.head.as_ref();
    while let Some(elem) = stack.pop() {
        if let Some(node) = curlink {
            if node.elem != elem {
                return false;
            }
            curlink = node.next.as_ref();
        }
    }

    true
}

/// 将单向链表按某值划分成左边小、中间相等、右边大的形式
/// 【题目】
/// 给定一个单向链表的头节点 head，节点的值类型是整型，再给定一个整数 pivot。
/// 实现一个 调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，
/// 中间部分都是值等于 pivot 的 节点，右部分都是值大于 pivot 的节点。除这个要求外，对调整后的节点顺序没有更多的要求。
/// 例如:链表 9->0->4->5->1，pivot=3。
/// 调整后链表可以是 1->0->4->9->5，也可以是 0->1->9->5->4。总之，满足左部分都是小于 3 的节点，
/// 中间部分都是等于 3 的节点(本例中这个部分为空)，右部分都是大于 3 的节点即可。 对某部分内部的节点顺序不做要求。
/// 普通解法：把链表中的数据放入数组中，再用快速排序的思路对数组中的数据分区（乱序）
/// 进阶算法：用small、equal、greater三个链表（原序）
fn partition_list_disorder(list: &mut RcList, pivot: i32) {
    if list.head.is_none() {
        return;
    }

    let mut help: Vec<i32> = vec![];
    let mut curlink = list.head.clone();
    while let RcLink(Some(node)) = curlink {
        help.push(node.borrow().elem);
        curlink = node.borrow().next.clone();
    }

    parition_vec(&mut help, pivot);

    curlink = list.head.clone();
    for e in help {
        if let RcLink(Some(node)) = curlink {
            node.borrow_mut().elem = e;
            curlink = node.borrow().next.clone();
        }
    }
}

fn parition_vec(v: &mut Vec<i32>, pivot: i32) {
    // 用pivot对help数组分区，分成小于、等于、大于3个区
    let mut gtc: usize = v.len(); // close闭区间 [gtc,...), 当前就是大于pivot的元素
    let mut lto: usize = 0; // open开区间 [..., lto)，前一个才是小于pivot的元素
    let mut idx: usize = 0;
    while idx < gtc {
        match v[idx].cmp(&pivot) {
            Ordering::Less => {
                v.swap(lto, idx);
                lto += 1;
                idx += 1
            }
            Ordering::Equal => idx = idx + 1,
            Ordering::Greater => {
                gtc -= 1;
                v.swap(gtc, idx);
            }
        }
    }
}

/// 将单向链表按某值划分成左边小、中间相等、右边大的形式
/// 进阶算法：用small、equal、greater三个链表（原序）
/// 进阶解法的具体过程如下：
/// 1．将原链表中的所有节点依次划分进三个链表，三个链表分别为 small 代表左部分，equal
/// 代表中间部分，big 代表右部分。
/// 例如，链表 7->9->1->8->5->2->5，pivot=5。在划分之后，small、equal、big 分别为：
/// small：1->2->null
/// equal：5->5->null
/// big：7->9->8->null
/// 2．将 small、equal 和 big 三个链表重新串起来即可。
/// 3．整个过程需要特别注意对 null 节点的判断和处理
fn partition_list_order(list: &mut RcList, pivot: i32) {
    let mut sh: RcLink = RcLink(None); // small head
    let mut st: RcLink = RcLink(None); // small tail
    let mut eh: RcLink = RcLink(None);
    let mut et: RcLink = RcLink(None);
    let mut gh: RcLink = RcLink(None);
    let mut gt: RcLink = RcLink(None);

    let mut curlink: RcLink = list.head.clone();

    while let RcLink(Some(node)) = curlink {
        curlink = node.borrow().next.clone();
        node.borrow_mut().next = RcLink(None);

        match node.borrow().elem.cmp(&pivot) {
            Ordering::Less => {
                if sh.is_none() {
                    sh = RcLink(Some(node.clone()));
                    st = sh.clone();
                } else {
                    if let RcLink(Some(st_node)) = st {
                        st_node.borrow_mut().next = RcLink(Some(node.clone()));
                        st = st_node.borrow().next.clone();
                    }
                }
            }

            Ordering::Equal => {
                if eh.is_none() {
                    eh = RcLink(Some(node.clone()));
                    et = eh.clone();
                } else {
                    if let RcLink(Some(et_node)) = et {
                        et_node.borrow_mut().next = RcLink(Some(node.clone()));
                        et = et_node.borrow().next.clone();
                    }
                }
            }
            Ordering::Greater => {
                if gh.is_none() {
                    gh = RcLink(Some(node.clone()));
                    gt = gh.clone();
                } else {
                    if let RcLink(Some(gt_node)) = gt {
                        gt_node.borrow_mut().next = RcLink(Some(node.clone()));
                        gt = gt_node.borrow().next.clone();
                    }
                }
            }
        }
    }

    st.as_ref()
        .map(|node| node.borrow_mut().next = if eh.is_some() { eh.clone() } else { gh.clone() });
    et.as_ref().map(|node| node.borrow_mut().next = gh.clone());
    list.head = if sh.is_some() {
        sh
    } else {
        if eh.is_some() {
            eh
        } else {
            gh
        }
    }
}

pub fn coding2_main() {
    println!("=========== 删除倒数第K个节点 ============");
    let mut list1 = List::new();
    let mut list2 = List::new();
    let nums = random_num(0..10);
    let arr = random_array(nums, 0..10);
    let last_k = random_num(0..nums) as i32;
    for e in arr {
        list1.push(e);
        list2.push(e);
    }
    println!("list: {}", list1);
    println!("删除倒数第{}个", last_k);
    remove_last_k(&mut list1, last_k);
    println!("remove backwards {} list: {}", last_k, list1);
    remove_last_k_pointer(&mut list2, last_k);
    println!("remove backwards {} list: {}", last_k, list2);

    println!("=========== 删除中间节点 ============");
    for i in 1..6 {
        let mut list = List::new();
        for j in 1..=i {
            list.push(j);
        }
        print!("list: {} ", list);
        remove_middle_node(&mut list);
        println!("删除中间后：{}", list);
    }

    for (a, b) in [(5, 7), (5, 6), (4, 6), (3, 6), (2, 6), (1, 6), (1, 7)] {
        let mut list = List::new();
        for i in 1..=7 {
            list.push(i);
        }
        print!("a:{}, b:{} ", a, b);
        remove_node_partition(&mut list, a, b);
        println!("{}", list);
    }

    println!("=========== 翻转链表 ============");
    let mut list = List::new();
    for j in 1..=7 {
        list.push(j);
    }
    println!("list: {}", list);
    rev_list(&mut list);
    println!("rev: {}", list);

    println!("=========== 翻转部分链表 ============");
    let mut list = RcList::new();
    for j in 1..=4 {
        list.push(j);
    }
    println!("list: {}", list);
    for end in 0..6 {
        let mut list = RcList::new();
        for j in 1..=4 {
            list.push(j);
        }
        print!("翻转[{}, {}]: ", 1, end);
        rev_part_list(&mut list, 1, end);
        println!("rev: {}", list);
    }

    println!("=========== 环形单链表的约瑟夫问题 ============");
    let nums = random_num(0..10);
    let step = random_num(0..10);
    let mut list = RcList::new();
    for i in 1..=nums {
        list.push(i);
    }
    let tail = list.tail();
    tail.as_ref()
        .map(|node| node.borrow_mut().next = list.head.clone());
    println!("{}, step: {}", list, step);
    josephus_kill(&mut list, step);
    println!("last: {}", list);

    println!("=========== 单向链表按值分区 ============");
    let nums = random_num(0..10);
    let max_val = random_num(0..100);
    let pivot = random_num(0..10);
    let arr = random_array(nums, 0..max_val);

    let mut list_disorder = RcList::new();
    let mut list_order = RcList::new();
    list_disorder.from_array(&arr);
    list_order.from_array(&arr);
    println!("pivot: {} | list: {}", pivot, list_order);
    partition_list_disorder(&mut list_disorder, pivot);
    println!("pivot: {} | 分区(无序): {}", pivot, list_disorder);
    partition_list_order(&mut list_order, pivot);
    println!("pivot: {} | 分区(有序): {}", pivot, list_order);
}

#[cfg(test)]
mod 链表 {
    use super::*;

    #[test]
    fn 删除倒数第k个节点() {
        for _ in 0..1000 {
            let mut list1 = List::new();
            let mut list2 = List::new();
            let nums = random_num(0..10);
            let arr = random_array(nums, 0..10);
            let last_k = random_num(0..nums) as i32;
            for e in arr {
                list1.push(e);
                list2.push(e);
            }
            assert_eq!(
                remove_last_k(&mut list1, last_k),
                remove_last_k_pointer(&mut list2, last_k)
            )
        }
    }

    #[test]
    fn 反转单向链表() {
        for _ in 0..1000 {
            let mut list1 = List::new();
            let mut arr1: Vec<i32> = vec![];
            let mut arr2: Vec<i32> = vec![];
            let nums = random_num(0..10);
            let arr = random_array(nums, 0..10);
            for &e in &arr {
                list1.push(e);
            }
            rev_list(&mut list1);
            for &e in arr.iter().rev() {
                arr2.push(e);
            }
            let mut cur = list1.head.as_mut();
            while let Some(node) = cur {
                arr1.push(node.elem);
                cur = node.next.as_mut();
            }
            assert_eq!(arr1, arr2);
        }
    }

    #[test]
    fn 反转部分单向链表() {
        for _ in 0..2000 {
            let mut list1 = RcList::new();
            let mut arr1: Vec<i32> = vec![];
            let mut arr2: Vec<i32> = vec![];
            let nums = random_num(0..10);
            let arr = random_array(nums, 0..10);
            let from = random_num(0..nums + 3);
            let to = random_num(from..nums + 3);
            for &e in &arr {
                list1.push(e);
                arr2.push(e);
            }
            rev_part_list(&mut list1, from, to);
            let mut cur = list1.head.clone();
            while let RcLink(Some(node)) = cur {
                arr1.push(node.borrow().elem);
                cur = node.borrow().next.clone();
            }
            rev_part_vec(&mut arr2, from, to);
            assert_eq!(arr1, arr2);
        }
    }
}
